Fibonomials: a Fibonacci form of the Binomial numbers

Aims
This is a page about generalising the Fibonacci Formula F(n)=F(n-1)+F(n-2) to a similar relationship but on the powers of the Fibonacci numbers: F(n)² and F(n)³ and so on.
Background
The material on this page assumes that you already know a little about the Fibonacci Numbers from Fibonacci Numbers, Golden Section and the Golden String (which contains a much fuller treatment of Fibonacci numbers and their mathematical properties) and are familiar with polynomials and algebra at school level age 14-15.
This page is an Appendix to those web pages, covering extra material aimed at the level of students in school aged 15-17.

Introduction

On this page we will introduce you to the Fibonacci Factorial function F!(n) and the Fibonomial array of numbers, so called because the Fibonomials are like the Binomial coefficients of Pascal's Triangle.
From the formula F(n)=F(n-1) + F(n-2) connectng three consecutive Fibonacci numbers, we find one connecting four consecutive F(n)² terms, five consecutive F(n)³ terms, six consecutive F(n)⁴ terms and so on. These are called Recurrence Relations (or Recursion Equations) since they are not explicit formulae that give F(n)² or F(n)³ in terms of n but in terms of some preceding terms in the F(n)^p series. Finally we uncover the formula for connecting any p+2 consecutive p-th powers of Fibonacci numbers. You will also discover the powerful mathematical technique of examining a series by making the numbers in the series into the coefficients of a polynomial in x, called the Power Series of the sequence.
Often we can then find a simple mathematical expression for that polyomial called its Generating Function. This is similar to relating the (infinite) sequence 3,7,0,3,7,0,... with first the (infinite) decimal fraction 0.370370370... and then the (finite) fraction ¹⁰/₂₇.

Contents of this Page

Recurrence Relations
Powers of Fibonacci Numbers
The Recurrence Relations for Powers of Fibonaccis
A Formula for the Fibonacci Powers' Recurrence Relations
More on the Fibonomials and the Binomials
Generating Functions for Powers of Fibonacci Numbers
More Generating Functions and the Fibonomials
- Fibonomial Row Generating Functions
- Fibonomial Column Generating Functions
  - Generating Functions for Binomial Columns
  - Generating Functions for Fibonomial Columns
Some ideas for experiments of your own:
Links and References

Recurrence Relations

For the Fibonacci numbers themselves, if we know any two consecutive terms then we can add them to get the next which we express in mathematical notation as:

F(n) = F(n-1) + F(n-2)

We have also seen that there are many such series, the General Fibonacci series, and we need to state two starting terms to determine one particular sequence. For the Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, 13, ... , these two starting conditions could be:-

F(0)=0, F(1)=1

For the Lucas Numbers: 2, 1, 3, 4, 7, 11, ..., we have

L(n) = L(n-1) + L(n-2); L(0)=2, L(1)=1

Such a formula for a series which defines each number in it in terms of some combination of previous terms is called a recurrence relation or recurrence formula.
For a series S this means defining S(n) in terms of some combination of previous terms S(n-1), S(n-2) down to S(0), though it may not always use all of the previous terms to define the next.

On this page we find simple recurrence relations for the F(n)² series, F(n)³ series and the other powers of the Fibonacci numbers. The pattern we end up with turns out to have some nice parallels with the Binomial Coefficients (the numbers in Pascal's Triangle) and introduces us to the Fibonomials.

Let's start with the squares of Fibonacci numbers:

Powers of Fibonacci Numbers

In this section we look at the series of squares of Fibonacci numbers then later at the cubes and higher powers.

Squares of Fibonacci Numbers and a Recurrence Relation

For the squares of the Fibonacci numbers we have:

n	1	2	3	4	5	6	7	...
F(n)	1	1	2	3	5	8	13	...
F(n)²	1	1	4	9	25	64	169	...

The recurrence relationship for F(n)² is not too easy to spot. However, it has been found already:

F(n)² = 2 F(n – 1)² + 2 F(n – 2)² – F(n – 3)²

The recurrence relation tells us how to find F(n)² using the previous 3 terms of the F(n)-squared series: F(n-1)², F(n-2)², F(n-3)²

double the latest term: 2 F(n-1)²
double the one before the latest: 2 F(n-2)² and add these
finally subtract the term two before the latest: F(n-3)²

For example: to find the next term after 1, 1, 4, 9 :

double the latest term: 2 F(n-1)² = 2×9 = 18
double the one before the latest: 2 F(n-2)² = 2×4 = 8 and add these
finally subtract the term two before the latest: F(n-3)² = 1

25 = 2×9 + 2×4 - 1 = 25 which is correct since it is F(5)²

Repeat the process now to find the next term following 1, 1, 4, 9, 25:

64 = 2x25 + 2x9 - 4

Now we have 1, 1, 4, 9, 25: the next is

2x64 + 2x25 - 9 = 128 + 50 - 9 = 169 which is indeed F(7)²=13²

It is easy to use a spreadsheet to generate the F(n)-squared series using the previous 3 cells in the list and so generate the series of squares of Fibonacci numbers.

It will be useful later to look at this equation with all the Fibonacci terms on one side:

F(n)² – 2 F(n – 1)² – 2 F(n – 2)² + F(n – 3)² = 0

Let's have a look at the Cubes of the Fibonacci numbers next.

The Cubes of the Fibonacci Numbers and their Recurrence Relation

n	1	2	3	4	5	6	7	...
F(n)	1	1	2	3	5	8	13	...
F(n)³	1	1	8	27	125	512	2197	...

The rule here was found by Zeitlin and Parker and published in the Fibonacci Quarterly in 1963:

F(n)³ = 3 F(n – 1)³ + 6 F(n – 2)³ – 3 F(n – 3)³ – F(n – 4)³

Check it for yourself or using a spreadsheet again.

Again, we write it with all the terms on one side as we did for the Squares:

F(n)³ – 3 F(n – 1)³ – 6 F(n – 2)³ + 3 F(n – 3)³ + F(n – 4)³ = 0

Our list of recurrence relationships for the powers from 1 to 3 now looks like this:

F(n) – F(n – 1) – F(n – 2) = 0
F(n)² – 2 F(n – 1)² – 2 F(n – 2)² + F(n – 3)² = 0
F(n)³ – 3 F(n – 1)³ – 6 F(n – 2)³ + 3 F(n – 3)³ + F(n – 4)³ = 0

Does the pattern generalise?

Fourth Powers

Does the pattern generalise? If so the next one would look something like

F(n)⁴ + A F(n – 1)⁴ + B F(n – 2)⁴ + C F(n – 3)⁴ + D F(n – 4)⁴ + E F(n – 5)⁴ = 0

Like the earlier formulae, we want this to hold for all values of n.
We have 5 numbers A, B, C, D and E to find and we can find them by solving some simultaneous equations if we put in some small values for n. Since our recurrence will hold for all values of n, it must also hold for the simple cases of n=5:

F(5)⁴ + A F(4)⁴ + B F(3)⁴ + C F(2)⁴ + D F(1)⁴ + E F(0)⁴ = 0 Using numeric Fib values:
5⁴ + A 3⁴ + B 2⁴ + C 1⁴ + D 1⁴ + E 0⁴ = 0 Evaluating the powers:
625 + A 81 + B 16 + C 1 + D 1 + E 0 = 0
625 + 81A + 16B + C + D = 0

We can do this for n=6, 7, 8 and 9 also so that we have 5 equations in the 5 variables A, B, C, D and E and we can then solve these.
It's a bit of a task doing this by hand and a computer algebra package (such as Derive, Maple or Mathematica) saves us a lot of time and, let's face it, is probably more accurate than doing it by hand too!
Either way we get the following values for the coefficients:

A = –5, B = –15, C = 15, D = 5, E = –1

If we put these 5 numbers into the suggested recurrence relationship above, we can evaluate a few more terms and see that it holds not just for n = 5, 6, 7, 8 and 9 but it looks as if it holds for all values of n:

F(n)⁴ – 5 F(n – 1)⁴ – 15 F(n – 2)⁴ + 15 F(n – 3)⁴ + 5 F(n – 4)⁴ – F(n – 5)⁴ = 0

We will prove this later.

Fifth Powers

The same method gives a recurrence formula for F(n)⁵:

F(n)⁵ – 8 F(n – 1)⁵ – 40 F(n – 2)⁵ + 60 F(n – 3)⁵ + 40 F(n – 4)⁵ – 8 F(n – 5)⁵ – F(n – 6)⁵ = 0

The Recurrence Relations for Powers of Fibonaccis

In this section we show how to find a general formula for the recurrence relations for F(n)^p using p for the power. Our list now looks like this:

F(n) – F(n – 1) – F(n – 2) = 0
F(n)² – 2 F(n – 1)² – 2 F(n – 2)² + F(n – 3)² = 0
F(n)³ – 3 F(n – 1)³ – 6 F(n – 2)³ + 3 F(n – 3)³ + F(n – 4)³ = 0
F(n)⁴ – 5 F(n – 1)⁴ – 15 F(n – 2)⁴ + 15 F(n – 3)⁴ + 5 F(n – 4)⁴ – F(n – 5)⁴ = 0
F(n)⁵ – 8 F(n – 1)⁵ – 40 F(n – 2)⁵ + 60 F(n – 3)⁵ + 40 F(n – 4)⁵ – 8 F(n – 5)⁵ – F(n – 6)⁵ = 0

If we look at the coefficients in these recurrences we have:

1	-1	-1
1	-2	-2	1
1	-3	-6	3	1
1	-5	-15	15	5	-1
1	-8	-40	60	40	-8	-1

These coefficients are called the Fibonomial numbers because they share many properties with the binomial numbers (binomial coefficients). So let's look at the Binomial numbers in more detail.

The Binomial Coefficients

Perhaps this reminds you of Pascal's Triangle which is usually shown in one of these two forms:

	col=		0	1	2	3	4	5	...
1	r o w	0	1
1 1		1	1	1
1 2 1		2	1	2	1
1 3 3 1		3	1	3	3	1
1 4 6 4 1		4	1	4	6	4	1
1 5 10 10 5 1		5	1	5	10	10	5	1
...		...	...

On an earlier page at this site we looked at the patterns in this table and found the Fibonacci numbers.
The rows of Pascal's Triangle are expansions of powers of a binomial term - a term with two parts such as (1+x):-

(1+x)⁰ =	1
(1+x)¹ =	1	+x
(1+x)² =	1	+ 2 x	+ 1 x²
(1+x)³ =	1	+ 3 x	+ 3 x²	+ 1 x³
(1+x)⁴ =	1	+ 4 x	+ 6 x²	+ 4 x³	+ 1 x⁴
(1+x)⁵ =	...

Here the x's are numbers (any number) rather than terms in a series that our recurrence relations deal with. The formula for the pattern in our new table is similar to that of the Binomial numbers.
In Pascal's triangle, the binomial coefficient on row n and column k is written as follows and has the following formula:

(	n	)
	k

n!	=	n . (n–1) . (n–2) ... (n–k+1)

k! (n–k)!		k. (k–1). ... 2. 1

n! is the factorial of n (n is a whole number) and is just the product of all the numbers from n down to 1. For example,

1! = 1
2! = 2 × 1 = 2
3! = 3 × 2 × 1 = 6
4! = 4 × 3 × 2 × 1 = 24
5! = 5 × 4 × 3 × 2 × 1 = 120

You might think that since this definition involves a fraction then for some values of n and k then the result will be a fraction not a whole number – but it is always a whole number! The numbers on the bottom will always "cancel" or be factors of those on the top.
For instance,

(	5	)
	3

5!	=	5 × 4 × 3 × 2 × 1	=	5 × 4	=	10

3! (5 – 3)!		(3 × 2 × 1) (2 × 1)		2 × 1

and the number on the row labelled 5 and column labelled 3 in Pascal's Triangle is 10.

Note that we have a special case when n is 0 or n=k: we have to let 0! mean 1 in the binomial coefficient formula to get the numbers shown in Pascal's Triangle.

Sometimes, to save room on a printed page, the binomial coefficient is written as _nC_k or ⁿC_k or even as binomial(n,k).
It is read as "n choose k" because given n different objects it is the number of ways we can choose k of them.

For instance, given the 5 objects A, B, C, D and E, we can choose a set of three of them in the following ₅C₃ = 10 ways:
ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE

The pattern in our table of coefficients for recurrence relations of F(n)^P needs two more ideas first: the Fibonacci Factorial and the Fibonomial.

The Fibonacci Factorial

Instead of n! which is the product of all the numbers from n down to 1, we now introduce the Fibonacci Factorial n !_F which is the product of the Fibonacci numbers from F(n), F(n-1) down to F(1).
There is no commonly accepted notation for the Fibonacci Factorial. Simon Plouffe uses a nicer notation: FF(n) although even better is F!(n). Since the latter is more readable, we will use F!(n) on this page.

n !_F or F!(n) stands for F(n) F(n-1) F(n-2) ... F(2) F(1)

For example:

F!(1) = 1
F!(2) = F(2) F(1) = 1 × 1 = 1
F!(3) = F(3) F(2) F(1) = 2 × 1 × 1 = 2
F!(4) = F(4) F(3) F(2) F(1) = 3 × 2 × 1 × 1 = 6
F!(5) = F(5) F(4) F(3) F(2) F(1) = 5 × 3 × 2 × 1 × 1 = 30

Here is a table of the first 20 Fibonacci Factorials with their factors: Note: It makes formulae simpler if we let F!(0) be a special case and define F!(0) to be 1 instead of the more logical value of 0.

n	F!(n)	F!(n) factors
0	1	1
1	1	1
2	1	1
3	2	2
4	6	2 3
5	30	2 3 5
6	240	2⁴ 3 5
7	3120	2⁴ 3 5 13
8	65520	2⁴ 3² 5 7 13
9	2227680	2⁵ 3² 5 7 13 17
10	122522400	2⁵ 3² 5² 7 11 13 17
11	10904493600	2⁵ 3² 5² 7 11 13 17 89
12	1570247078400	2⁹ 3⁴ 5² 7 11 13 17 89
13	365867569267200	2⁹ 3⁴ 5² 7 11 13 17 89 233
14	137932073613734400	2⁹ 3⁴ 5² 7 11 13² 17 29 89 233
15	84138564904377984000	2¹⁰ 3⁴ 5³ 7 11 13² 17 29 61 89 233
16	83044763560621070208000	2¹⁰ 3⁵ 5³ 7² 11 13² 17 29 47 61 89 233
17	132622487406311849122176000	2¹⁰ 3⁵ 5³ 7² 11 13² 17 29 47 61 89 233 1597
18	342696507457909818131702784000	2¹³ 3⁵ 5³ 7² 11 13² 17² 19 29 47 61 89 233 1597
19	1432814097681520949608649339904000	2¹³ 3⁵ 5³ 7² 11 13² 17² 19 29 37 47 61 89 113 233 1597
20	9692987370815489224102512784450560000	2¹³ 3⁶ 5⁴ 7² 11² 13² 17² 19 29 37 41 47 61 89 113 233 1597

This is A003266 in Sloane's Online Encyclopedia of Integer Sequences.

A Formula for the Fibonomial

Now we define a new form of "binomial coefficient" but using this definition of factorial instead. We will use a subscript "F" after the binomial brackets to distinguish it from the binomial coefficient itself:

(	n	)_F
	k

F!(n)

F!(k) F!(n – k)

F(n)F(n–1)...F(n–k+1)F(n–k)F(n–k–1)...F(2)F(1)

F(k)F(k–1)...F(2)F(1) F(n–k)F(n–k–1)...F(2)F(1)

There is no universal notation for the Fibonomial. D Knuth and others use double brackets:	((	n	))
		k

A simple alternative is to write fibonomial(n,k) which has the advantage of using less space on the page. Here is a table of some values of the fibonomial

		k
		0	1	2	3	4	5	6	7
n	1	1	1
	2	1	1	1
	3	1	2	2	1
	4	1	3	6	3	1
	5	1	5	15	15	5	1
	6	1	8	40	60	40	8	1
	7	1	13	104	260	260	104	13	1

The above appears as A010048 in Sloane's Online Encyclopedia of Integer Sequences (OEIS).

To get the signed Fibonomials, all the numbers in every other pair of columns after the first column are negated:

		k
		0	1	2	3	4	5	6	7
n	1	1	–1
	2	1	–1	–1
	3	1	–2	–2	1
	4	1	–3	–6	3	1
	5	1	–5	–15	15	5	–1
	6	1	–8	–40	60	40	–8	–1
	7	1	–13	–104	260	260	–104	–13	1

The signed table is A055870 in Sloane's OEIS.

How can we tell if a Fibonomial is negative in this table?

The negative columns occur in pairs between two positive columns. How can we incorporate this into our formulae? We can use the rounding functions and here we introduce you two three of them: round, floor, ceiling.

The Rounding Functions: round, floor and ceiling

The most common rounding funciton is perhaps round(x) which "rounds" a real-number value x to the nearest whole number.
There are two other kinds of rounding too: round-up or ceiling(x) and round-down or floor(x).

For example, when we pay for an item in a shop, we must round-up the price to present a whole number of pound coins:
an item costing £3.80 can be paid for with 4 pound coins. Even an item costing £3.01 must be rounded-up to 4 pound coins.
We write this as ceiling(3.80) = ceiling(3.01) = 4

On the other hand, having bought an item and paid for it, giving change involves the round-down function:
If the customer is needs £3.80 in change, we give 3 pound coins (and 80 pence).
Similarly for change to the value of £3.01.
We write this as floor(3.80) = floor(3.01) = 3

The third everyday case is when a friend, admiring your wise purchase, asks how much it cost. We would often just give a rough figure to the nearest whole number of pounds).

If it cost £3.80 we would say "around 4 pounds"
if £3.01 then "about 3 pounds".

We have rounded to the nearest whole number of pounds.
We write this as round(3.80)=4; round(3.01)=3 If the cost was £3.50 then we would have to decide if we said £3 or £4 since both 3 and 4 are equally close to 3.50.

Rounding negative values

When we round a negative value, we have to be careful about the floor and ceiling values. We adopt the common convention that:
floor(x) is the next whole number less than (more negative than) x.
ceiling(x) is the next whole number greater than (more positive than) x.
round(x) is still the closest whole number and we must decide what to do about values such as 3.5 and -7.5 which are exactly half-way between two whole number values.
For whole numbers x, the result of all of these functions is x itself.
e.g.

Result ->	2	1	0	-1	-2
floor	floor(2.9) floor(2.1) floor(2)	floor(1.9) floor(1.3) floor(1.1) floor(1)	floor(0.8) floor(0.4) floor(0)	floor(-0.2) floor(-0.8) floor(-1)	floor(-1.2) floor(-1.9) floor(-2)
ceiling	ceiling(1.9) ceiling(1.3) ceiling(1.1) ceiling(2)	ceiling(0.8) ceiling(0.4) ceiling(1)	ceiling(-0.2) ceiling(-0.9) ceiling(0)	ceiling(-1.2) ceiling(-1.9) ceiling(-1)	ceiling(-2.8) ceiling(-2.4) ceiling(-2)
round	round(2.1) round(1.9) round(2)	round(1.3) round(0.8) round(1)	round(0.4) round(-0.2) round(0)	round(-0.8) round(-1.2) round(-1)	round(-1.9) round(-2.3) round(-2)

Why call these functions floor and ceiling?

Because we can image an object held at height n on a vertical number line with "floors" at the whole number levels.
For the floor function, the object is heavy so it falls to the next whole number floor level if it is not already at a whole number on the line.
For the ceiling function, imagine a helium-filled balloon which rises from height n to the next whole number above it if not already at a whole number height.
Tis is shown in the diagram at the side of the Table above.

Floor or Trunc?

For positive values of x floor(x) means the same as "forget anything after the decimal point" and may be called trunc for "truncate" on some calculators. Beware of using the "trunc" button on negative values as trunc(-2.8) may produce -2 by truncating the value at the decimal point whereas floor(-2.8) is -3.

A formula for the sign of a Fibonomial

We want a pair of values to be positive as k increases, then a pair of negative and so on across each row.
The columns with the negative signs are k=1,2, (not 3 or 4) 5,6, (not 7 or 8) 9, 10, .... we can do this using powers of -1 and the pairing of values is done using a rounding function.

Here is what happens is we use k/2 in the floor function as our power of (-1):

k	0	1	2	3	4	5	6	7	8
k/2	0	0.5	1	1.5	2	2.5	3	3.5	4
floor(k/2)	0	0	1	1	2	2	3	3	4
(-1)^floor(k/2)	1	1	-1	-1	1	1	-1	-1	1

This is not quite what we want: we can

EITHER use k+1 instead of k: (-1)^{floor((k+1)/2)}
OR use the ceiling function: (-1)^ceiling(k/2)

k	0	1	2	3	4	5	6	7	8
k/2	0	0.5	1	1.5	2	2.5	3	3.5	4
ceiling(k/2)	0	1	1	2	2	3	3	4	4
(-1)^ceiling(k/2)	1	-1	-1	1	1	-1	-1	1	1

This now gives us a formula (a way of predicting) the sign of the coefficient in the recurrence relations. Now we look at the coefficients themselves, the Fibonomials.

A Recurrence Relation for the Fibonomials

Each binomial coefficient can be found by using the two numbers above it when each row is centred or, when the table is laid out with vertical columns, the number above and the number to the left of that one.
Those two numbers and merely added:

	col=		0	1	2	3	4	5	...
1	r o w	0	1
1 1		1	1	1
1 2 1		2	1	2	1
1 3 3 1		3	1	3	3	1
1 4 6 4 1		4	1	4	6	4	1
1 5 10 10 5 1		5	1	5	10	10	5	1
...		...	...

There is a way of calculating each Fibonomial in terms of the two on the row above it too, but it involves the Fibonacci numbers too:

Row 4	1		3		6		3		1
	\| 1 \|	\ 5 \	\| 0 \|	\ 3 \	\| 1 \|	\ 2 \	\| 1 \|	\ 1 \	\| 2 \|	\ 1 \
Row 5	1x1 =1	1x5+3x0 =5		3x3+6x1 =15		6x2+3x1 =15		3x1+1x2 =5		1x1 =1

To find the Fibonomials on row 5 from those on row 4, the two series of numbers used are 1 0 1 1 2 ... and ... 5 3 2 1 1
The second series (using the number above) starts with F(n) on row n and goes down.

Row n=5:

k=0:	0	+ 1×F(-1)	= 1;
k=1:	1×F(5)	+ 3×F(0)	= 5;
k=2:	3×F(4)	+ 6×F(1)	= 15;
k=3:	6×F(3)	+ 3×F(2)	= 15;
k=4:	3×F(2)	+ 1×F(3)	= 5;
k=5:	1×F(1)	+ 0	= 1

D E Knuth (The Art of Computer Programming, Vol. 1 Fundamental Algorithms, Section 1.2.8 Exercise 27) gives the formula for this method as

fibonomial( n, k ) = F( n – k + 1 ) fibonomial( n – 1, k – 1 ) + F( k – 1 ) fibonomial( n – 1, k )

Note that the indexes of the two Fibonacci multipliers always sum to n, the row number of the (new) Fibonomial.
Compare this with the much simpler formula for the binomial coefficients where we merely add the two numbers on the row above to get each term:

(	n	)
	k

(	n – 1	)
	k

(	n – 1	)
	k – 1

A Sequence of Power Formulas Bro A Brousseau The Fibonacci Quarterly vol 6 (1968) pages 81-83: took essentially the same approach as shown above and found a recursive method of generating the power formula, but did not explicitly give the recursion.

Later on this page we will find Fibonomial formula that are very similar to their binomial counterparts, but first, let's put all the above together and show the complete formula for our Fibonacci Power recurrence relations.

A Formula for the Fibonacci Powers' Recurrence Relations

D E Knuth (ibid. Exercise 30) also gives the full formula for the recurrences we found for the Fibonacci Powers, and our form here is slightly simpler than his but is essentially the same form:

k=0

(	p	)_F
	k

(-1)^ceiling(k/2)F(n – k)^p-1

= 0, if p>0

More on the Fibonomials and the Binomials

Symmetric Rows

The rows of Pascal's Triangle and the rows in our Fibonomial Triangle are symmetrical.
In mathematical terms we express this as:

binomial( n, k ) = binomial( n, n – k)
Fibonomial( n, k ) = Fibonomial( n, n – k)

Relationship with term before

Each term on a row can be computed directly from the term before it on the same row:

(	n	)
	k

n – k + 1

(	n	)
	k – 1

, k

(	n	)_F
	k

F( n – k + 1)

F( k )

(	n	)_F
	k – 1

, k

Relationship with term above

Each term can be computed from the one "above" (in the same column):

(	n	)
	k

n – k

(	n – 1	)
	k

, k

(	n	)_F
	k

F( n )

F( n – k )

(	n – 1	)_F
	k

, k

Generating Functions for Powers of Fibonacci Numbers

Sometimes it helps to solve a mathematical problem if we relate a series to a polynomial in x with the series as the coefficients. Such a series is called a Power Series and often we can find a simple expression for the (infinite) power series. Here are some examples:

A Generating Function for the Fibonacci Numbers

The Fibonacci numbers (omitting 0): 1, 1, 2, 3, 5, ...
As a Power Series: 1 + 1 x + 2 x² + 3 x³ + 5 x⁴ + ...

But

1 – x – x²

= 1 + 1 x + 2 x² + 3 x³ + 5 x⁴ + ...

so the generating function for the Fibonacci numbers is

1 – x – x²

On an earlier page we gave a simple proof and saw how we could use this series and its shorter generating function to find decial fractions which are the Fibonacci numbers .
By letting x= 0.1 in the generating function we have a fraction 1/ (1 - 0.1- 0.01 = 100/(100-10-1) = 100/89.
Looking at this fraction in terms of its power series, we have 0.1 + 0.01 + 0.002 + 0.0003+ ... = 0.11235...
Letting x=0.01 and x=0.001 give the decimal fractions 0.101020305081321... and 0.1001002003005008013021... and so on.

What happened to the missing first term of 0? If you want to restore it, then the power series is 0 + 1 x + 1 x² + 2 x³ + 3 x⁴ + ...
All we have done is multiply the series by x!

So, with the extra 0 term at the start, the generating function is
x
1 – x – x²

A Generating Function for the Squares of the Fibonacci Numbers

Can we find a generating function for the series F(n)²? Yes - here it is:
The series F(n)²: 1, 1, 2² = 4, 3² = 9, 5² = 25, ...

As a Power Series: 1 + 1 x + 4 x² + 9 x³ + 25 x⁴ + ...

The generating function is

1 – x

1 – 2 x – 2 x² + x³

More Generating Functions for Powers of Fibonacci Numbers

Here is a table summarising the above results and extending them

Fibonacci terms

Generating Function

x⁰

x¹

x²

x³

x⁴

x⁵

...

F(n)

...

1 – x – x²

F(n)²

...

1 – x

1 – 2 x – 2 x² + x³

F(n)³

125

512

...

1 – 2 x – x²

1 – 3 x – 6 x² + 3 x³ + x⁴

F(n)⁴

625

4096

...

1 – 4 x – 4 x² + x³

1 – 5 x – 15 x² + 15 x³ + 5 x⁴ – x⁵

F(n)⁵

243

3125

32768

...

1 – 7 x – 16 x² + 7 x³ + x⁴

1 – 8 x – 40 x² + 60 x³ + 40 x⁴ – 8 x⁵ – x⁶

Did you notice that the polynomials in the denominators all have coefficients which are just a row of the Fibonomial Table?

More Generating Functions and the Fibonomials

If we return to our Fibonomial Table, they have some more surprises for us when we see what polynomials they form when we use them as coefficients, that is, what are the generating functions for the Fibonomial rows and columns.

Fibonomial Row Generating Functions

With the signs, we have the following table, witht he k value telling us which coefficient of x we use for the numbers in its column in order to make a polynomial in x - its Generating Function (G.F.)

n	Fibonomial Row as a GF	Factors
1	1–1x	1–x
2	1–1x–1x²		1–x–x²
3	1–2x–2x²+1x³	1+x		1–3x+x²
4	1–3x–6x²+3x³+1x⁴		1+x–x²		1–4x–x²
5	1–5x–15x²+15x³+5x⁴–1x⁵	1–x		1+3x+x²		1–7x+x²
6	1–8x–40x²+60x³+40x⁴–8x⁵–1x⁶		1–x–x²		1+4x–x²		1–11x–x²
7	1–3x–104x²+260x³+260x⁴–104x⁵–13x⁶+1x⁷	1+x		1–3x+x²		1+7x+x²		1–18x+x²

The factors of the GF polynomials have some interesting relationships:

All the factors are linear or quadratic
The linear factors are (1 ± x)
Each new row introduces one new quadratic factor
All the factors of the GF of row n-2 are, with some sign changes, factors of the GF of row n
The quadratic factors are all of the form 1 ± A x ± x²
The coefficients of x in the quadratic factors are the Lucas Numbers:
0 1 2 3 4 5 6 ...

2 1 3 4 7 11 18 ...

The factors that are "copied" from the row two before have changed the sign of the coefficients of x, but the constant terms (1) and the x² terms remain unaltered.
An easy way to express this is that the "x" has been replaced by "-x".
If FGF(n,x) means the Fibonomial Generating Function (i.e. the polynomial) of row n in the Table above, then we can express all the observations in the list as follows:

FGF(1, x) = 1 – x
FGF(2, x) = 1 – x – x²
FGF(n, x) = FGF(n–2, –x) ( 1 – L(n – 1)x + (–1)ⁿ⁺¹ x²), n > 2

This result is given as a comment on A055870. noting that the result is derivable from the Knuth and Riordan references which are at the foot of this page.

Row Factors and Phi

The quadratic factors can be factored further into two real roots as follows where, as usual on these pages Phi = (√5 + 1)/2, phi = (√5 – 1)/2

–1 – x + x² = (x – Phi)(x – (–phi))	–1 + x + x² = (x + Phi)(x + (–phi))
1 – 3 x + x² = (x – Phi²)(x – (–phi)²)	1 + 3 x + x² = (x + Phi²)(x + (–phi)²)
–1 – 4 x + x² = (x – Phi³)(x – (–phi)³)	–1 + 4 x + x² = (x + Phi³)(x + (–phi)³)
1 – 7 x + x² = (x – Phi⁴)(x – (–phi)⁴)	1 + 7 x + x² = (x + Phi⁴)(x + (–phi)⁴)
...
(–1)ⁿ – L(n) + x² = (x – Phiⁿ)(x – (–phi)ⁿ)	(–1)ⁿ + L(n) x + x² = (x + Phiⁿ)(x + (–phi)ⁿ)

Underlying this is this simple formula for the Lucas Numbers L(n) in terms of the golden section numbers Phi and phi:

L(n) = Phiⁿ + (–phi)ⁿ

Fibonomial Column Generating Functions

We will compare the generating functions for the columns of Pascal's Triangle (binomial coefficients) with the generating functions for the Fibonomials.

Generating Functions for Binomial Columns

The columns of Pascal's Triangle are the generating functions of some simple polynomials:

Pascal's
Triangle

c o l

...

r
o
w

...

1–x

(1–x)²

(1–x)³

(1–x)⁴

(1–x)⁵

(1–x)⁶

...

Here, 1/(1–x) = 1 + x + x² + x³ + x⁴ +... so the coefficients are 1, 1, 1, 1, 1, ... which is the first column.
1/(1–x)² = 1 + 2 x + 3 x³ + 4 x⁴ + 5 x⁵ +... and the coefficients here are 1, 2, 3, 4, 5, .... which is the second column, and so on.

Note that if we let x have a numerical value, then they are only true if –1 < x < 1. However, we are merely using the expansion as a convenient mathematical expression which is a "holder" for the infinite series of numbers.
For instance, let x=0.1 = 1/10 in 1/(1–x). This fraction is then 1/0.9=10/9=1 + 1/9. The GF expansion gives 1 + 1×0.1 + 1×0.01 + ... = 1.11111... which is correct as the decimal fraction for 10/9.
Try it for other values to see a numerical fraction and its expansion.
If we let x=0.01=1/100 in the second column's GF, we have the decimal fraction 1.02030405060708091011... and the GF fraction is 1/(1–0.01)²=(100/99)²=10000/9801

Generating Functions for Fibonomial Columns

Here is a table of the columns of Fibonomials as coefficients of (rational) functions of x:

Fibonomials

c o l

...

r
o
w

...

1 – x

1–x–x²

1–2x–2x²+x³

1–3x–6x²+3x³+x⁴

1–5x–15x²+15x³+5x⁴–x⁵

...

Did you notice that the polynomials in the denominators have coefficients which are themselves Fibonomials?
Stuart Eugene Thiel proved it but then found an earlier proof was published in The generalized Fibonomial matrix by E. Kilic in European Journal of Combinatorics, vol 31 (2010) pages 193-209.

Things to do

Find a recurrence relationship between every other Fibonacci number squared:
F(1)², F(3)², F(5)², ,...
Find a recurrence relationship between the other series of alternate Fibonacci squares:
F(2)², F(4)², F(6)², ,...
What about every third Fibonacci cubed? There are three series to try:
F(0)³, F(3)³, F(6)³, ,...
F(1)³, F(4)³, F(7)³, ,...
F(2)³, F(5)³, F(8)³, ,...
Is the recurrence the same in each case?
What about fourth powers?
What is the general pattern?

Links and References

The Art of Computer Programming D E Knuth, Volume 1: Fundamental Algorithms (now in its Third Edition, 1997).
Knuth gives a proof of our main result in the Answers section for the Exercise in which it appears and attributes the result to D. Jarden.
The full reference for D Jarden's paper is given in Concrete Mathematics as reference 194 and is given below:

The product of sequences with a common linear recursion formula of order 2 Dov Jarden, Theodor Motzkin, Riveon Lematematika vol 3 (1949), pages 25-27 and 38 (Hebrew with English summary); and in English translation :

Fibonacci Powers and a Fascinating Triangle Dale K Hathaway, Stephen L. Brown The College Mathematics Journal 28 (1997), pages 124-128.

Recurring Sequences Dov Jarden, (second edition 1966), pages 30-33 - now out of print - and in the first edition 1958, pages 42-45.

Generating functions for powers of Fibonacci numbers by J. Riordan, Duke. Math. J. vol 29 (1962) pages 5-12.

Fibonacci - the man and His Times Fibonacci Home Page
The Lucas Numbers

WHERE TO NOW???
General Fibonacci Series
Fibonacci, Phi and Lucas numbers Formulae
Links and References

		k
		0	1	2	3	4	5	6	7
n	1	1	1
	2	1	1	1
	3	1	2	2	1
	4	1	3	6	3	1
	5	1	5	15	15	5	1
	6	1	8	40	60	40	8	1
	7	1	13	104	260	260	104	13	1

		k
		0	1	2	3	4	5	6	7
n	1	1	1
	2	1	1	1
	3	1	2	2	1
	4	1	3	6	3	1
	5	1	5	15	15	5	1
	6	1	8	40	60	40	8	1
	7	1	13	104	260	260	104	13	1

		k
		0	1	2	3	4	5	6	7
n	1	1	1
	2	1	1	1
	3	1	2	2	1
	4	1	3	6	3	1
	5	1	5	15	15	5	1
	6	1	8	40	60	40	8	1
	7	1	13	104	260	260	104	13	1